Complexidade SL

Na teoria da complexidade computacional, SL (Logspace Simétrica ou Sym-L) é a classe de complexidade dos problemas de log-espaço redutível a USTCON (não-s-t conectividade), é o problema de determinar se existe um caminho entre dois vértices em um grafo não direcionado, caso contrário, descrito como o problema de determinar se dois vértices estão no mesmo componente conectado. Este problema também é chamado de problema da não-acessibilidade. Embora originalmente descrita em termos de máquinas simétricas de Turing, é equivalente a formulação uma muito complexa, e a definição de redutibilidade é o que é usado na prática.

USTCON é um caso especial de STCON (acessibilidade dirigida), o problema de determinar se um caminho dirigido entre dois vértices em um grafo direcionado existe, que é completa para o NL. USTCON é SL-completa, a maioria dos avanços mostram que o impacto USTCON têm também um impacto SL. Assim, eles são conectados, e discutidos em conjunto.

Em outubro de 2004 Omer Reingold mostrou que SL = L.